package com.wcj.test;

import java.util.Arrays;

/**
 * 给你一个整数 n ，表示一个国家里的城市数目。城市编号为 0 到 n - 1 。
 *
 * 给你一个二维整数数组 roads ，其中 roads[i] = [ai, bi] 表示城市 ai 和 bi 之间有一条 双向 道路。
 *
 * 你需要给每个城市安排一个从 1 到 n 之间的整数值，且每个值只能被使用 一次 。
 * 道路的 重要性 定义为这条道路连接的两座城市数值 之和 。
 *
 * 请你返回在最优安排下，所有道路重要性 之和 最大 为多少。
 */
public class 道路的最大总重要性 {

    public long maximumImportance(int n, int[][] roads) {
        long[] map = new long[n];
        for (int i = 0; i < roads.length; i++){
            map[roads[i][0]]++;
            map[roads[i][1]]++;
        }
        int num = 1;
        Arrays.sort(map);
        long ans = 0L;
        for (int i = 0; i < map.length; i++){
            ans += map[i]*num;
            num++;
        }
        return ans;
    }
}
